package com.fr.lintcode;

import java.util.HashMap;
import java.util.Map;

public class Q442 {

    public class Trie {

        private Node root;

        public Trie() {
            // do intialization if necessary
            root = new Node();
        }

        /*
         * @param word: a word
         * @return: nothing
         */
        public void insert(String word) {
            // write your code here
            Node node = root;
            for (char c : word.toCharArray()) {
                Node tmp = node.child.get(c);
                if (tmp == null) {
                    tmp = new Node();
                    tmp.c = c;
                    node.child.put(c, tmp);
                }
                node = tmp;
            }
            node.end = true;
        }

        /*
         * @param word: A string
         * @return: if the word is in the trie.
         */
        public boolean search(String word) {
            // write your code here
            Node node = root;
            for (char c : word.toCharArray()) {
                node = node.child.get(c);
                if (node == null) {
                    return false;
                }
            }
            return node.end;
        }

        /*
         * @param prefix: A string
         * @return: if there is any word in the trie that starts with the given prefix.
         */
        public boolean startsWith(String prefix) {
            Node node = root;
            for (char c : prefix.toCharArray()) {
                node = node.child.get(c);
                if (node == null) {
                    return false;
                }
            }
            return node != null;
        }

        public class Node {
            char c;
            boolean end;
            Map<Character, Node> child = new HashMap<>();
        }

    }

}
